package class_0918btree;
import java.util.ArrayList;
import java.util.List;
public class BTree<K extends Comparable<K>,V> {
    public static class Node<K,V>{
        K key;
        V value;
        boolean isLeaf;
        List<Node<K,V>> entry;
        List<Node<K,V>> children;
        public Node(K key, V value){
            this(key,value,false);
        }
        public Node(K key, V value, boolean isLeaf){
            this.key = key;
            this.value = value;
            this.isLeaf = isLeaf;
            this.entry = new ArrayList<Node<K,V>>();
            this.children = new ArrayList<Node<K,V>>();
        }

        public K getKey(){
            return key;
        }

        public V getValue(){
            return value;
        }

        public V setValue(V value){
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean isLeaf(){
            return isLeaf;
        }

    }

    private Node<K,V> root;
    private static int DEFAULT_MIN = 2;
    private int m;//B树的阶数
    private int min;//最小度数
    public BTree(){
        this(2*DEFAULT_MIN);
    }
    public BTree(int m){
        root = null;
        this.m = m;
        this.min = (int)Math.ceil(m*1.0/2)+1;
    }

    public Node<K,V> search(K key){
        return searchRec(root, key);
    }

    public Node<K,V> searchRec(Node<K,V> cur, K key){
        int i=0;
        int n = cur.entry.size();
        while(i<n && key.compareTo(cur.entry.get(i).key)>0){
            i++;
        }
        if(i<n && key.compareTo(cur.entry.get(i).key)==0){
            return cur;
        }
        if(cur.isLeaf){
            return null;
        }
        return searchRec(cur.children.get(i), key);
    }

    public Node<K,V> searchUnRec(Node<K,V> cur, K key){
        int i,n;
        while(true){
            i=0;
            n = cur.entry.size();
            /* */
            while(i<n && key.compareTo(cur.entry.get(i).key)>0){
                i++;
            }
            if(i<n && key.compareTo(cur.entry.get(i).key)==0){
                return cur;
            }
            if(cur.isLeaf){
                return null;
            }
            cur = cur.children.get(i);
        }
    }

    public boolean contains(K key){
        return searchRec(root, key)!=null;
    }

    public void split(Node<K,V> parent,int i){
//        Node<K,V> right = new Node<>();

    }

    public void insert(K key, V value){

    }
}
